package com.captain.leetcode2.链表;

import com.captain.leetcode.链表.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * <p>
 * 图示两个链表在节点 c1 开始相交：
 */
public class 相交链表160 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //用hash记录走过的路,每次都去检查一下, 如果存在有,那么则相交
        Map<ListNode, Object> map = new HashMap<>();
        while (headA != null || headB != null) {
            if (headA != null) {
                if (map.containsKey(headA)) return headA;
                map.put(headA, new Object());
                headA = headA.next;
            }
            if (headB != null) {
                if (map.containsKey(headB)) return headB;
                map.put(headB, new Object());
                headB = headB.next;
            }
        }
        return null;
    }

}
